<?php

/**
 * 原理：是对冒泡排序的一种改进。（若序列已然有序那么就和冒泡排序一样了）通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
 */
class 快速排序
{
    public function 运行($输入数组)
    {
        $数组长度 = count($输入数组);

        if ($数组长度 <= 1) {
            return $输入数组;
        }

        $基准数字 = $输入数组[0];

        $左边数组 = [];
        $右边数组 = [];
    

        for ($i = 1; $i < $数组长度; $i++) {
            if ($输入数组[$i] < $基准数字) {
                $左边数组[] = $输入数组[$i];
            } else {
                $右边数组[] = $输入数组[$i];
            }
        }

        $左边数组 = $this->运行($左边数组);
        $右边数组 = $this->运行($右边数组);

        return array_merge($左边数组, [$基准数字], $右边数组);
    }
}

$输入数组 = [5, 9, 6, 3, 1];
$实例 = new 快速排序();

$结果数组 = $实例->运行($输入数组);

print_r($结果数组);